1. Field of the Invention
The present invention relates to communications; more particularly, an efficient automatic repeat request method.
2. Description of the Prior Art
FIG. 1 illustrates transmitter 10 and receiver 20. Data messages are communicated from transmitter 10 to receiver 20, and feedback regarding the reception of the data messages is provided from receiver 20 to transmitter 10. The bytes in the data message are numbered sequentially to identify them uniquely at the transmitter and the receiver. The data messages from transmitter 10 to receiver 20 typically include a header field, a sequence number field, a field for bytes of data and a CRC (cyclic redundant code) field. The header field provides information such as information indicating whether the data message contains new data or a retransmission of data that was corrupted in an earlier transmission. The sequence number field contains a sequence number that identifies the bytes of data contained in the message. For example, the sequence number may identify the sequence number of the first byte of data in the data field. The second through last byte of data in the data field are associated with sequence numbers that begin with the sequence number plus 1 and continuing consecutively until a number is associated with the last data byte. The data field contains the bytes of data being transmitted from the transmitter to the receiver, and the CRC field contains a code used to detect and sometimes correct errors in the data message. When receiver 20 receives the data message, it uses the CRC field to determine whether errors have occurred. If errors have occurred, the receiver uses the sequence number field in a subsequent transmission to identify a sequence number associated with byte or bytes of data that were received incorrectly. The receiver provides feedback to transmitter 10 by sending a ACK (acknowledgment) or NAK (negative acknowledge) message to transmitter 10. The negative acknowledge message typically includes two fields: a header field, and a sequence number and length field. Header field provides information such as information indicating that the NAK message is identifying incorrectly received data bytes, or that the NAK message is providing control information to the transmitter. The sequence number and length field include a sequence number that identifies the first byte of data that was received incorrectly and the length portion identifies the number of bytes following the sequence number that were not received or received with errors. Transmitter 10 uses the sequence number and length in the NAK message to identify bytes of information to be retransmitted in another data message to receiver 20. In a data message containing data that is being retransmitted, the header field will indicate that the data message is a retransmission of prior data that was not received properly by receiver 20. The sequence number of retransmitted bytes will be the same that was used when the data bytes were originally transmitted to receiver 20. Again, the sequence number field contains a sequence number that identifies the bytes of retransmitted data contained in the message; for example, the sequence number of the first byte. The remaining bytes are consecutive.
FIG. 2 illustrates high rate and low rate data message. A high rate data message has a header field, the sequence number field, a data field and a CRC field. It should be noted that sequence number field typically includes three bytes, and in the case of a high data rate transfer, a data field may include as many as 4,000 bytes. From a point of view of efficiency, using 3 bytes for a sequence number with 4,000 bytes of information can be considered an efficient transfer. Conversely, the low rate message is inefficient. In this case, three bytes per sequence number are used to identify only 21 bytes in a data transfer message. As a result, the present scheme for providing sequence numbers used in automatic repeat request schemes are not suitable for transmission protocols that involve variable rate transmissions where messages may include either a large number of bytes or a small number of bytes.
The present invention solves the aforementioned problem by providing a variable length sequence number. The sequence number associated with the most recent data that has been received successfully and the sequence number expected with the next data message to be received are examined to determine the minimum size sequence number necessary to unambiguously identify incorrectly received data that will be retransmitted in a later message. The receiver periodically provides the transmitter with the sequence number associated with the last successfully received byte of data and the sequence number associated with the next expected byte of data. The receiver communicates this information to the transmitter using a control message. The transmitter then uses the sequence number of the next byte of data to be transmitted and the information received in the control message from the receiver to determine the smallest number of bits necessary to represent the sequence numbers for both data transmissions and the retransmission of data that was not received properly by the receiver.
V(S)xe2x88x92VT(R) less than 2mxe2x80x83xe2x80x83(1)
Equation 1 specifies the smallest m number of bits that may be used to represent the sequence number for new data being transmitted to a receiver. V(S) represents the sequence number that the transmitter will associate with the next byte of data to be transmitted and VT(R) represent the sequence number received in the control message that identifies the next byte of data expected to be received at the receiver.
V(S)xe2x88x92VT(N) less than 2nxe2x80x83xe2x80x83(2)
Equation 2 indicates the smallest value of n that can be used to represent a sequence number used to retransmit data to a receiver. In equation 2, VT(N) is the sequence number received in the control message from the receiver that identifies the last successfully received byte of data by the receiver.